/*
 *  src/algorithms/binary_search.c
 *
 *  Harry Wei <harryxiyou@gmail.com> (C) 2011
 */
#include <glib.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

int bs(int *datas, int find, int len)
{
	int left = 0;
	int right = len - 1;

	if (NULL == datas || (0 == len)) {
		g_message("%s -- error!\n", __func__);
		return -1;
	}
	while (left <= right) {
		int middle = (int) ((left + right) / 2);
		if (find == datas[middle]) {
			return middle;
		} else if (find > datas[middle]) {
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
	g_message("%s -- Can not find this number!", __func__);
	return -1;
}

int bs_newer(int *datas, int find, int len)
{
	int left = 0;
	int right = len - 1;

	if (NULL == datas || (0 == len)) {
		g_message("%s -- error!\n", __func__);
		return -1;
	}
	int i = 0;
	for (i = 0; i < len; i++) {
		g_message("%d ", datas[i]);
	}
	while (left <= right) {
		int middle = (int) ((left + right) / 2);
		if (find == datas[middle]) {
			return middle;
		} else if (find > datas[middle]) {
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
	g_message("%s -- Can not find this number!", __func__);
	g_message("%s -- We should get the similar number!", __func__);
	left = 0;
	right = len - 1;
	if (find < datas[0]) {
		g_message("%s -- lower than the first element!", __func__);
		return 0;
	}
	g_message("find is %d, datas[len - 1] is %d", find, datas[len - 1]);
	if (find > datas[len - 1]) {
		g_message("%s -- higher than the last element!", __func__);
		return len - 1;
	}
	while (1) {
		int middle = (int) ((left + right) / 2);
		if (find > datas[middle]) {
			if (find < datas[middle + 1]) {
				return middle;
			} else {
				left = middle + 1;
			}
		}
		if (find < datas[middle]) {
			if (find > datas[middle - 1]) {
				return middle - 1;
			} else {
				right = middle - 1;
			}
		}
	}
	g_message("%s -- beyond my thoughts ;-)", __func__);
	return -1;
}
